package q647_countSubstrings;

public class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        /*
        此题关键在于遍历顺序
        我们用dp[i][j]代表 从 i 到 j 这一段字符串是否为回文字符串 左右都为闭区间
        在判断回文字符串时如果是 a 或者 aa 这样的 也就是j - i <= 1 那显然是一个回文字符串
        而超过1时 就要判断dp[i + 1][j - 1] 如果是true 那么当然dp[i][j]也为true

        所以遍历顺序就不能从上到下 从左到右了
        观察dp的表 可以发现实际上dp[i + 1][j - 1] 在 dp[i][j]的左下⻆
        所以我们要从左下开始遍历
         */
        for (int i = dp.length - 1; i >= 0; i--) {
            for (int j = i; j < dp.length; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
//                    if (j - i <= 1) {
//                        res++;
//                        dp[i][j] = true;
//                    }else if (dp[i + 1][j - 1]) {
//                        res++;
//                        dp[i][j] = true;
//                    }
                    // 上面的判断简化到一个if中即可
                    res++;
                    dp[i][j] = true;
                }
            }
        }

        return res;
    }
}
